\section{Introducing the algorithms}

In this chapter, we introduce each of the standard algorithms. The groups of algorithms are arbitrary and mainly introduced for presentation clarity. Therefore, you might correctly argue that a specific algorithm would be better suited to reside in a different group.

Before we start, we will use the \cpp{std::for_each} and \cpp{std::for_each_n} algorithms to demonstrate this chapter's structure for each algorithm.

\begin{enumerate}[label=\protect\circled{\arabic*}]
    \item The presentation of each algorithm will start with a short description.
    \item The margin will contain information about the history of the algorithm: which C++ standard introduced it and whether it has constexpr, parallel and range variants and including versions of the standard that introduced them.
    \item Following that will be the description of constraints. Algorithms that write data to a distinct output range are denoted with an arrow: \newline\cpp{input_range -> output_range}.
    \item Finally, each description will conclude with one or more examples with explanations.
\end{enumerate}

\subsection{\texorpdfstring{\cpp{std::for_each}}{\texttt{std::for\_each}}}
\index{\cpp{std::for_each}}

\circled{1} The \cpp{std::for_each} algorithm applies the provided invocable to each element of the range in order. If the underlying range is mutable, the invocable is permitted to change the state of elements but cannot invalidate iterators.

\cppversions{\circled{2} \texttt{std::for\_each}}{\CC98}{\CC20}{\CC17}{\CC20}

% Custom table to inject the circled number.
\begin{center}
\footnotesize
\begin{tabular}{|m{\dimexpr.22\textwidth-2\tabcolsep}|m{\dimexpr.30\textwidth-2\tabcolsep}|m{\dimexpr.45\textwidth-2\tabcolsep}|}
\hline
\rowcolor{black!80} \multicolumn{3}{l}{\textcolor{white}{\circled{3} constraints}} \\
\hline
domain & \multicolumn{2}{m{\dimexpr.75\textwidth-2\tabcolsep}|}{\cpp{input_range}} \\
\hline
parallel domain & \multicolumn{2}{m{\dimexpr.75\textwidth-2\tabcolsep}|}{\cpp{forward_range}} \\
\hline
\multirow{2}{.15\textwidth}{invocable} & \cellcolor{black!80} \textcolor{white}{default} & \cellcolor{black!80} \textcolor{white}{custom} \\
\cline{2-3}
& N/A & \cpp{unary_invocable} \\
\hline
\end{tabular}
\end{center}

\circled{4} The C++11 standard introduced the range-based for loop, which mostly replaced the uses of \cpp{std::for_each}.

\begin{codebox}[]{\href{https://compiler-explorer.com/z/b6qEoonno}{\ExternalLink}}
\footnotesize Example of a range loop over all elements of a \cpp{std::vector}.
\tcblower
\cppfile{code_examples/algorithms/for_each_code_range.h}
\end{codebox}

\begin{codebox}[]{\href{https://compiler-explorer.com/z/M38M379To}{\ExternalLink}}
\footnotesize Example of a \cpp{std::for_each} loop over all elements of a \cpp{std::vector}.
\tcblower
\cppfile{code_examples/algorithms/for_each_code_simple.h}
\end{codebox}

However, there are still a few corner cases when using \cpp{std::for_each} is preferable.

The first case is straightforward parallelization. Invoking an expensive operation for each element in parallel is trivial with \cpp{std::for_each}. As long as the operations are independent, there is no need for synchronization primitives.

\begin{codebox}[breakable]{\href{https://compiler-explorer.com/z/3bq4xT3G9}{\ExternalLink}}
\footnotesize Example of a parallel \cpp{std::for_each} invoking a method on each element independently in parallel.
\tcblower
\cppfile{code_examples/algorithms/for_each_code_parallel.h}
\end{codebox}

Second, the range version can provide a more concise and explicit syntax in some cases because of the projection support introduced in C++20.

\begin{codebox}[]{\href{https://compiler-explorer.com/z/sfxWa4T5f}{\ExternalLink}}
\footnotesize Example of the range version of \cpp{std::ranges::for_each}  utilizing a projection to invoke the method \cpp{getValue()} (line 13) on each element and summing the resulting values using a lambda (line 12).
\tcblower
\cppfile{code_examples/algorithms/for_each_code_cpp20.h}
\end{codebox}

\subsection{\texorpdfstring{\cpp{std::for_each_n}}{\texttt{std::for\_each\_n}}}
\index{\cpp{std::for_each_n}}

\circled{1} The \cpp{std::for_each_n} algorithm applies the provided invocable to each element of the range specified using an iterator and the number of elements. If the underlying range is mutable, the invocable is permitted to change the state of elements but cannot invalidate iterators.

\cppversions{\circled{2} \texttt{for\_each\_n}}{\CC17}{\CC20}{\CC17}{\CC20}

% Custom table to inject the circled number.
\begin{center}
\footnotesize
\begin{tabular}{|m{\dimexpr.22\textwidth-2\tabcolsep}|m{\dimexpr.30\textwidth-2\tabcolsep}|m{\dimexpr.45\textwidth-2\tabcolsep}|}
\hline
\rowcolor{black!80} \multicolumn{3}{l}{\textcolor{white}{\circled{3} constraints}} \\
\hline
domain & \multicolumn{2}{m{\dimexpr.75\textwidth-2\tabcolsep}|}{\cpp{input_iterator}} \\
\hline
parallel domain & \multicolumn{2}{m{\dimexpr.75\textwidth-2\tabcolsep}|}{\cpp{forward_iterator}} \\
\hline
\multirow{2}{.15\textwidth}{invocable} & \cellcolor{black!80} \textcolor{white}{default} & \cellcolor{black!80} \textcolor{white}{custom} \\
\cline{2-3}
& N/A & \cpp{unary_invocable} \\
\hline
\end{tabular}
\end{center}

\circled{4} While \cpp{std::for_each} operates on the entire range, the interval $[begin, end)$, \cpp{std::for_each_n} operates on the range $[first, first+n)$. Importantly, because the algorithm does not have access to the end iterator of the source range, it does no out-of-bounds checking, and it is the responsibility of the caller to ensure that the range $[first, first+n)$ is valid.

\raggedbottom

\begin{codebox}[]{\href{https://compiler-explorer.com/z/o8rEzc6q3}{\ExternalLink}}
\footnotesize Example demonstrating multiple uses of \cpp{std::for_each_n}.
\tcblower
\cppfile{code_examples/algorithms/for_each_n_code.h}
\end{codebox}

 Sending invitations to the \texttt{MAIN\_SEATS} top players is done in parallel (lines 4-7). Then all users' scores are stored in chunks of \texttt{PAGE\_SIZE} records (lines 13-15). Note that calculating the remaining number of elements (line 12) and jumping ahead by the number of stored elements (line 17) requires a random access iterator (in this case, provided by \cpp{std::vector}).